package org.zjt.ds;

import java.util.Arrays;

/**
 * @author juntao.zhang
 * @version V1.0
 * @Description: 快排算法
 *               用pivot划分，将左右按照大小pivot交换。并得到partition index。按照index拆分为更小的数组。
 * @Package org.zjt.ds
 * @date 2018/4/22 21:44
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] data = new int[]{5,1,3,1,4};
        int intPartition = intPartition(data, 2, 0, data.length - 1);
        System.err.println(intPartition);
        doQuickSort(data);
        Arrays.stream(data).forEach(System.out::println);
    }


    public static void doQuickSort(int[] data) {
        doQuickSort(data,0,data.length-1);
    }

    /**
     * 快速排序的实现
     * @param data
     * @param start
     * @param end
     */
    public static void doQuickSort(int[] data,int start,int end) {
        if (start >= end )return;
        else{

            //将划分后的元素数组，再进行划分比较。例如两个元素在一起。比较得到最小的值。
            int indexPartition = intPartition(data, data[end], start, end);
            doQuickSort(data,start,indexPartition-1);
            doQuickSort(data,indexPartition,end);
        }
    }

    /**
     * 划分。根据pivot划分。
     * 将左边大于pivot的元素和右边小于pivot的值交换。（从外到内）
     * @param data
     * @param pivot
     * @param start
     * @param end
     * @return
     */
    public static int intPartition(int[] data,int pivot,int start,int end) {
        int leftCursor  = start -1;
        int rightCursor  = end + 1;
        while (true){

            // 得到划分后，左边比pivot大的索引。
            while (data[++ leftCursor ] < pivot && leftCursor <= end);

            // 得到划分后，右边比pivot小的索引
            while (data[-- rightCursor] > pivot && rightCursor > -1);

            // 如果左边大于右边光标则退出
            if (leftCursor >= rightCursor)
                break;
            else
                swap(data,leftCursor,rightCursor);
        }
        return leftCursor;
    }

    private static void swap(int[] data, int leftCursor, int rightCursor) {
        int datum = data[leftCursor];
        data[leftCursor] = data[rightCursor];
        data[rightCursor] = datum;
    }

}
